Search results for "Standard Sturmian word"

showing 3 items of 3 documents

Standard Sturmian words and automata minimization algorithms

2015

The study of some close connections between the combinatorial properties of words and the performance of the automata minimization process constitutes the main focus of this paper. These relationships have been, in fact, the basis of the study of the tightness and the extremal cases of Hopcroft's algorithm, that is, up to now, the most efficient minimization method for deterministic finite state automata. Recently, increasing attention has been paid to another minimization method that, unlike the approach proposed by Hopcroft, is not based on refinement of the set of states of the automaton, but on automata operations such as determinization and reverse, and is also applicable to non-determ…

Discrete mathematicsTheoryofComputation_COMPUTATIONBYABSTRACTDEVICESNested wordFinite-state machineGeneral Computer ScienceAutomata minimizationComputer Science (all)ω-automatonNonlinear Sciences::Cellular Automata and Lattice GasesStandard Sturmian wordTheoretical Computer ScienceAutomatonCombinatoricsTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESDFA minimizationAutomata theoryQuantum finite automataBrzozowski's minimization algorithmTime complexityAlgorithmComputer Science::Formal Languages and Automata TheoryMathematicsTheoretical Computer Science
researchProduct

A combinatorial view on string attractors

2021

Abstract The notion of string attractor has recently been introduced in [Prezza, 2017] and studied in [Kempa and Prezza, 2018] to provide a unifying framework for known dictionary-based compressors. A string attractor for a word w = w 1 w 2 ⋯ w n is a subset Γ of the positions { 1 , … , n } , such that all distinct factors of w have an occurrence crossing at least one of the elements of Γ. In this paper we explore the notion of string attractor by focusing on its combinatorial properties. In particular, we show how the size of the smallest string attractor of a word varies when combinatorial operations are applied and we deduce that such a measure is not monotone. Moreover, we introduce a c…

General Computer ScienceSettore INF/01 - InformaticaString (computer science)de Bruijn word0102 computer and information sciences02 engineering and technologyCharacterization (mathematics)Burrows-Wheeler transform01 natural sciencesMeasure (mathematics)Standard Sturmian wordTheoretical Computer ScienceCombinatoricsConjugacy classMonotone polygonString attractor010201 computation theory & mathematicsAttractorThue-Morse word0202 electrical engineering electronic engineering information engineeringLempel-Ziv encoding020201 artificial intelligence & image processingWord (group theory)Mathematics
researchProduct

Special factors and the combinatorics of suffix and factor automata

2011

AbstractThe suffix automaton (resp. factor automaton) of a finite word w is the minimal deterministic automaton recognizing the set of suffixes (resp. factors) of w. We study the relationships between the structure of the suffix and factor automata and classical combinatorial parameters related to the special factors of w. We derive formulae for the number of states of these automata. We also characterize the languages LSA and LFA of words having respectively suffix automaton and factor automaton with the minimal possible number of states.

Special factorGeneral Computer ScienceSpecial factorsFactor automatonBüchi automatonω-automatonTheoretical Computer ScienceCombinatoricsDeterministic automatonTwo-way deterministic finite automatonNondeterministic finite automatonComputer Science::Data Structures and AlgorithmsCombinatorics on wordStandard Sturmian wordsMathematicsDiscrete mathematicsCombinatorics on wordsDAWGPushdown automatonComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)Nonlinear Sciences::Cellular Automata and Lattice GasesSuffix automatonProbabilistic automatonSuffix automatonComputer Science::Formal Languages and Automata TheoryComputer Science(all)Theoretical Computer Science
researchProduct